# 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
#  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
#  问总共有多少条不同的路径？
#
#  示例 1：
# 输入：m = 3, n = 7
# 输出：28
#
#  示例 2：
# 输入：m = 3, n = 2
# 输出：3
# 解释：
# 从左上角开始，总共有 3 条路径可以到达右下角。
# 1. 向右 -> 向下 -> 向下
# 2. 向下 -> 向下 -> 向右
# 3. 向下 -> 向右 -> 向下
#
#  示例 3：
# 输入：m = 7, n = 3
# 输出：28
#
#  示例 4：
# 输入：m = 3, n = 3
# 输出：6
from functools import lru_cache


class Solution:
    def uniquePaths2(self, m: int, n: int) -> int:
        """
        动态规划：
        要到达(i, j) 必须先到(i - 1, j)或者(i, j - 1)
        dp[i][j]表示从起点到(i, j)的路径数
        所以 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        :param m:
        :param n:
        :return:
        """
        dp = [[0 for __ in range(n)] for _ in range(m)]  # dp[i][j]表示从起点(0, 0)到(i, j)的路径数
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]

    def uniquePaths1(self, m: int, n: int) -> int:
        @lru_cache(None)
        def fn(i: int, j: int) -> int:  # fn(i, j)表示从起点(1, 1)到(i, j)的路径数
            if i == 1 or j == 1:
                return 1
            return fn(i - 1, j) + fn(i, j - 1)
        return fn(m, n)

    def uniquePaths(self, m: int, n: int) -> int:
        return self.uniquePaths1(m, n)


if __name__ == "__main__":
    m, n = 7, 3
    m, n = 3, 3
    print(Solution().uniquePaths(m, n))
